public class Test5 {
    //leetcode 416 分割等和子集
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int n : nums) sum += n;
        //因为题目中说了数组中的元素都是正整数，所以当数组所有元素的和为奇数的时候，一定不会在数组找到
        //和为sum/2的数字和
        if (sum % 2 == 1) return false;
        int n = nums.length, aim = sum / 2;
        boolean[] dp = new boolean[aim + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = aim; j >= nums[i-1]; j--) {
                //第i个数字可以选择也可以不选择，两种情况任意一种为true，那么dp[i][j]的值就为true
                dp[j] = dp[j] || dp[j - nums[i-1]];
            }
        }
        return dp[aim];
    }
}
